1. Field of the Invention
The present invention relates to an apparatus and method for tracking processing of a command.
2. Description of Related Art
Conventionally, in a data processing system, commands and associated data are transferred from caches and processors to other caches and processors using buffers. For instance, in one possible architecture two cache line buffers are connected to a level one cache, L1 cache, and a level two cache, L2 cache. These two line buffers are also connected to a main memory, a host processor, and possibly other processors via a system bus. When a command issues from one of the L1 cache, L2 cache or system bus, the L1 cache, L2 cache or system bus issuing the command is referred to as the command source. The one of the L1 cache, the L2 cache and the system bus to which the command is to be routed is referred to as the command sink. A cache line buffer allows for the smooth transition of data between components having different data transfer rates.
A conventional cache line buffer strictly handles either fill commands or cast back commands, and includes a memory space which can store a finite, for example, four, lines of cache pertaining to such commands. Each line of cache in a cache line buffer is, therefore, strictly designated as either a fill cache line or a cast back cache line.
When, for example, a request for data from the host processor to the L1 cache results in a miss, the L1 cache issues a fetch command to the L2 cache via a fill cache line buffer. The fetch command requests that the L2 cache provide the L1 cache with the missing cache line. In other words, the L1 cache is requesting to fill a cache line.
The L1 cache, however, may not have any space available to store the cache line requested. In this case, the L1 cache casts out a line of cache to make room for the expected new line of cache. This process is referred to as a cast back. If the cache line being cast back was modified while in the L1 cache, the cache line is sent via a cast back cache line buffer and the system bus to main memory to update the copy of this cache line in main memory; otherwise, the cache line is discarded. Typically, as discussed above, the conventional data processing system includes a fill cache line buffer and a cast back cache line buffer. Accordingly, the four lines of cache on the fill cache line buffer are designated as fill cache lines and the four lines of cache in the cast back cache line buffer are designated as cast back cache lines.
This strict cache line structure, however, poses problems. The fill cache line buffer can only handle at most four fetch commands at one time. The cast back cache line buffer cannot be used to handle a fifth fetch command, and as such, a fifth fetch command will have to await the availability of one of the fill cache lines. The same is true with respect to a fifth cast back command.
The conventional cache line buffer also includes a plurality of unidirectional queues for each command path. For instance, a fetch command from the L1 cache directed towards the L2 cache is placed in an L1-to-L2 queue, assuming a fill cache line is available. The fetch command will then be processed in due course based on the type of queue, e.g. FIFO, LIFO, etc. Similarly, unidirectional queues exist from each command source to each command sink. Consequently, besides the unidirectional L1-to-L2 queue the cache line buffer includes a unidirectional L2-to-L1 queue. Some cache line buffers, however, implement shared queues. For instance, some conventional cache line buffers use a shared queue for the command path from the system bus to the L1 cache and the command path from the system bus to the L2 cache.
The simple command queuing system of conventional cache line buffers posses problems. The use of a simple unidirectional queue from a command source to a command sink does not permit the processing of commands by priority, or easily permit dynamically changing the priority in which commands are processed. Furthermore, the processing of commands is not centrally tracked, and the cache line buffer provides no means of establishing ownership over the cache line residing therein. Such additional failings increase the difficulty and complexity of using data processing systems having conventional cache line buffers in multiprocessor systems. In multiprocessor systems, cache line ownership, established by associating a memory image coherency state, is important to the overall operation of the multiprocessor system. One example method is MESI, where MESI stands for modified, exclusive, shared and invalid.